# -*- coding:utf-8 -*-
# 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

# 示例 1：
# 输入：head = [1,2,3,3,4,4,5]
# 输出：[1,2,5]

# 示例 2：
# 输入：head = [1,1,1,2,3]
# 输出：[2,3]

# 提示：
# 链表中节点数目在范围 [0, 300] 内
# -100 <= Node.val <= 100
# 题目数据保证链表已经按升序 排列

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

# 快慢指针
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head == None:
            return head
        t = ListNode(head.val, head)
        slow = t
        fast = head.next
        need = False
        while fast != None:
            if fast.val == t.val:
                if fast.next == None and fast.val == t.val:
                    slow.next = None
                fast = fast.next
                need = True
                continue
            t.val = fast.val
            if need:
                slow.next = fast
                fast = fast.next
                need = False
                continue
            slow = slow.next
            fast = fast.next
            continue
        return t.next
  
# 查看题解找到的更加优雅的写法
# 这个思路的主要想法是把重复出现的节点，通过一个while把它当做逻辑上的一个节点进行处理  
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head == None:
            return head
        t = ListNode(None, head)
        slow = t
        fast = head
        while fast != None:
            while fast.next and fast.val == fast.next.val:
                fast = fast.next
            if slow.next == fast:
                slow = fast
            else:
                slow.next = fast.next
            fast = fast.next
        return t.next